package com.cheung.leetcode.str;

import org.junit.jupiter.api.Test;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.str
 * @Author :  cheungming
 * @CreateTime : 2024-05-10 15:49:27
 * @Description : 比较退格字符串
 * <p>
 * 双指针法——快慢指针
 * @Version : 1.0
 */
public class Code844Test {


    public boolean backspaceCompare(String s, String t) {
        int sL = s.length() - 1;
        int tL = t.length() - 1;
        int sSkip = 0;
        int tSkip = 0;

        // 双指针，从字符串最后往前遍历
        while (sL >= 0 || tL >= 0) {

            // 第一个指针sL指向字符串 s，索引指向不退格的字符
            while (sL >= 0) {

                if (s.charAt(sL) == '#') {
                    sSkip++;
                    sL--;
                } else if (sSkip > 0) {
                    sSkip--;
                    sL--;
                } else {
                    break;
                }
            }


            // 第一个指针tL指向字符串 t，索引指向不退格的字符
            while (tL >= 0) {
                if (t.charAt(tL) == '#') {
                    tSkip++;
                    tL--;
                } else if (tSkip > 0) {
                    tSkip--;
                    tL--;
                } else {
                    break;
                }
            }

            // 比较两个字符，如果不相同，直接返回false
            if (sL >= 0 && tL >= 0) {
                if (s.charAt(sL) != t.charAt(tL)) {
                    return false;
                }
            } else {

                if (sL >= 0 || tL >= 0) {
                    return false;
                }
            }

            sL--;
            tL--;
        }
        return true;
    }


    @Test
    public void test1() {
        String s = "ab#c", t = "ad#c";
        assert backspaceCompare(s, t);
    }


    @Test
    public void test2() {
        String s = "ab##", t = "c#d#";
        assert backspaceCompare(s, t);
    }

    @Test
    public void test3() {
        String s = "a#c", t = "b";
        assert !backspaceCompare(s, t);
    }

    @Test
    public void test4() {
        String s = "a#b", t = "b";
        assert backspaceCompare(s, t);
    }
}
